#include <iostream>
using namespace std;

const int MAX_SIZE = 100; // 最大的链表大小

// 定义一个静态链表节点
struct Node {
    int data;  // 数据域
    int next;  // 指针域，表示下一个节点的位置
};

class StaticLinkedList {
    private:
        Node data[MAX_SIZE]; 
        int head;             // 链表的头节点索引
        int avail;             // 空闲节点的索引

    public:
        StaticLinkedList() {
            // 初始化节点链表
            head = -1; // 初始化时链表为空
            avail = 0;  // 第一个空闲节点的索引为 0
            for (int i = 0; i < MAX_SIZE - 1; i++) {
                data[i].next = i + 1;  // 将所有空闲节点串联成链
            }
            data[MAX_SIZE - 1].next = -1; // 最后一个空闲节点指向 -1，表示空闲链表的末尾
        }

        // 插入元素到链表
        void insert(int value) {
            if (avail == -1) {
                cout << "链表已满，无法插入新元素" << endl;
                return;
            }

            int newIndex = avail;    // 分配一个新的节点
            avail = data[avail].next; // 更新空闲链表的头部

            data[newIndex].data = value; // 新节点赋值
            data[newIndex].next = head;  // 新节点的下一个指向当前头节点
            head = newIndex;              // 更新头节点为新插入的节点
        }

        // 打印静态链表
        void printList() {
            int current = head;
            while (current != -1) {
                cout << data[current].data << " -> ";
                current = data[current].next;
            }
            cout << "null" << endl;
        }

        void reverse() {
            int prev = -1;
            int current = head;
            while (current != -1) {
                int nextNode = data[current].next; // 记录下一个节点
                data[current].next = prev;         // 反转指针
                prev = current;                     // 前进到下一个节点
                current = nextNode;
            }
            head = prev;  // 更新头节点为最后一个节点
        }

};

int main(){
    StaticLinkedList list;
    list.insert(10);
    list.insert(20);
    list.insert(30);

    cout << "静态链表的元素为:         ";
    list.printList();
    cout<<"(2) 你能在静态链表上实现线性表的“逆置”算法吗？: ";
    list.reverse();
    list.printList();
    return 0;
}
